package algorithm.recurrence;

import sun.applet.Main;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * 汉诺塔
 *
 * @author 杨 强
 * @package algorithm.recurrence
 * @createTime 2023-03-08 21:48
 */
public class Hanoi {

    /**
     * 定义三根柱子
     */
    private static LinkedList<Integer> a = new LinkedList<>();
    private static LinkedList<Integer> b = new LinkedList<>();
    private static LinkedList<Integer> c = new LinkedList<>();

    public static void main(String[] args) {
        init(33);
        print();
        hanoi01(3, a, b, c);
    }

    /**
     * 初始化圆盘到a柱
     */
    private static void init(int n){
        for (int i = n; i > 0; i--) {
            a.addLast(i);
        }
    }

    /**
     * 打印三根柱子的状态
     */
    private static void print(){
        System.out.println(a.toString());
        System.out.println(b.toString());
        System.out.println(c.toString());
        System.out.println("==================================");
    }

    /**
     * 汉诺塔版本一
     *      有2个盘的时候移动的思路就是:
     *          先需要把1盘从a柱移动到b柱, 借助c柱
     *          然后把2盘从A柱移动到C柱, 借助B柱
     *          然后把1盘从B柱移动到C柱, 借助A柱
     * @param n 需要移动的圆盘个数, 数字越大说明圆盘越大, 比如n=2就是12个圆盘, 2是最大的盘子, 在a柱最下面
     * @param a 圆盘最开始的柱子
     * @param b 中间辅助的柱子
     * @param c 圆盘最的目标柱子
     */
    public static void hanoi01(int n, LinkedList<Integer> a, LinkedList<Integer> b, LinkedList<Integer> c){
        // n = 0的时候说明移动完毕
        if (n == 0){
            return;
        }

        // 先需要把1盘从a柱移动到b柱
        // 这时候n就等于2-1=1, 当n=1进入递归后, 1-1进入递归会直接返回, 所以直接执行, c.addLast(a.removeLast())
        // 就是直接把1盘从a移动到b, 然后退出, 然后这时候N=2, c.addLast(a.removeLast())又执行, 就把2盘从a柱移动到c柱,
        // 然后在执行最下面的递归函数, 这是啥2-1=1, 就是把1盘从b柱移动到c柱.
        hanoi01(n-1, a, c, b);

        // 然后把2盘从A柱移动到C柱, 这时候n=2, a.removeLast()就是2盘.
        c.addLast(a.removeLast());
        // 移动成功一个盘子从A柱到C柱就打印下三根柱子
        print();

        // 然后把1盘从B柱移动到B柱
        hanoi01(n-1, b, a, c);
    }
}
